package class_3;

import java.util.Arrays;
import java.util.Random;

public class Coding_mincostTickets2 {
	public static int MAX = 366;
	public static int[] dp = new int[MAX];
	public static int[] duringations = new int[] {1,7,30};
	public static int mincostTickets(int[] days,int[] costs) {
		int n = days.length;
		Arrays.fill(dp, 0, days.length+1, Integer.MAX_VALUE);
		dp[n] = 0;
		
		for(int i=n-1;i>=0;i--) {
			for(int k=0, j=i;k<3;k++) {
				while(j<days.length && days[i]+duringations[k]>days[j]) {
					j++;
				}
				dp[i] = Math.min(dp[i], costs[k]+dp[j]);
			}
		}
		return dp[0];
	}
	
	public static void main(String[] args) {
		int[] days = new int[30];
		int[] costs = new int[3];
		Random random = new Random();
		/**
		 * 利用随机数和排序生成符合题目条件的测试样例。---对数器
		 */
		for(int i=0;i<days.length;i++) {
			days[i] = random.nextInt(1,366);
		}
		Arrays.sort(days);
		for(int i=0;i<costs.length;i++) {
			costs[i] = random.nextInt(1,1001);
		}
		Arrays.sort(costs);
		System.out.println("days:"+ Arrays.toString(days));
		System.out.println("costs:" + Arrays.toString(costs));
		long startTime = System.nanoTime();
		int ret = mincostTickets(days, costs);
		long endTime = System.nanoTime();
		System.out.println("最低票价:"+ ret);
		System.out.println("自低向上共耗时"+ (endTime - startTime) + " 纳秒");
	}
}
